import java.util.ArrayList;
import java.util.HashMap;

/**
 * Created by zhangjinrui on 17/6/27.
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }

    public String toString(){
        ArrayList<String> ret = new ArrayList<>();
        ret.add(val + "");
        if(left != null) {
            ret.add(left.toString());
        }else{
            ret.add("[null]");
        }
        if(right != null) {
            ret.add(right.toString());
        }else{
            ret.add("[null]");
        }
        return ret.toString();
    }
}

public class Solution337 {

    public static void main(String args[]) {
        Solution337 s = new Solution337();
    }

    public int rob(TreeNode root) {
        int a = dfs(root, true);
        int b = dfs(root, false);
        return a > b ? a : b;
    }

    public int dfs(TreeNode root, boolean self) {
        if (root == null) {
            return 0;
        }
//        if (root.val < 0) {
//            return - root.val;
//        }
        if (self) {
            int ret = root.val + dfs(root.left, !self) + dfs(root.right, !self);
//            root.val = -ret;
            return ret;
        } else {
            int l = max(dfs(root.left, self), dfs(root.left, !self));
            int r = max(dfs(root.right, self), dfs(root.right, !self));
//            root.val = -(l + r);
            return l + r;
        }
    }

    public int max(int a, int b) {
        return a > b ? a : b;
    }

}
